class State {
  constructor(id, distFromStart) {
    this.id = id // 节点的id
    this.distFromStart = distFromStart // 从起点到节点的距离
  }
}
function dijkstra (start, end, graph) {
  let n = graph.length // 获得图的长度
  let distTo = new Array(n).fill(Infinity) // 初始化这个从起点到该节点的路径都是最大值
  distTo[start] = 0 // 起点到起点是0
  let pq = new myPriorityQueue() // 创建一个优先级队列
  pq.enqueue(new State(start, 0), 0) // 这个的优先级就是这个的distFromStart
  while (!pq.isEmpty()) { // 如果队列不是空的话
    let curState = pq.dequeue().element // 队列弹出
    let curNodeId = curState.id // 获得弹出的元素的id
    let curDistFromStart = curState.distFromStart // 获得从起点到这个元素的距离
    if (curNodeId === end) {
      return curDistFromStart // 如果这个当前的id是结尾的id 那么直接返回起点到这个元素的距离就好了
    }
    if (curDistFromStart > distTo[curNodeId]) {
      // 如果从起点到这个元素的距离 大于distTo数组中当前节点的距离 就直接进行下一次循环
      continue
    }
    for (let neighbor of graph[curNodeId]) { // 拿出这个节点所有的邻居
      let nextNodeId = neighbor[0] // 获得这个邻居的id
      let effortToNextNode = Math.max(
        distTo[curId],
        neighbor[1] // 从curId到nextId的权重
      ) // 计算从起始节点到这个节点的最短距离
      if (distTo[nextNodeId] > effortToNextNode) { // 如果现在的下一个节点的最短距离 大于从起始节点到该节点的距离
        distTo[nextNodeId] = effortToNextNode
        pq.enqueue(new State(nextNodeId, effortToNextNode), effortToNextNode) // 将当前的节点放入优先级队列 此时的权重是distToNextNode
      }
    }
  }
  return -1 // 返回结果数组 表示起点到各点的最短权重
}
//封装优先级队列，priority越小，优先级越高
function myPriorityQueue () {
  //存放每一个插入元素QueueElement
  this.items = [];
  //定义内部类--封装插入元素
  function QueueElement (element, priority) {
    this.element = element;
    this.priority = priority;
  }
  //实现插入操作
  myPriorityQueue.prototype.enqueue = function (element, priority) {
    var qe = new QueueElement(element, priority);
    if (this.items.length === 0) {
      this.items.push(qe);
    } else {
      var flag = false; //记录元素是否插入，没有就插入到items最后
      for (var i = 0; i < this.items.length; i++) {
        if (priority < this.items[i].priority) {
          this.items.splice(i, 0, qe);
          flag = true;
          break;
        }
      }
      if (!flag) {	//没有就插入到items最后
        this.items.push(qe);
      }
    }
  }

  //2.将元素从队列中移除
  myPriorityQueue.prototype.dequeue = function () {
    return this.items.shift();
  }
  //3.查看队列中第一个元素
  myPriorityQueue.prototype.front = function () {
    return this.items[0];
  }
  //4.查看队列是否为空
  myPriorityQueue.prototype.isEmpty = function () {
    return this.items.length === 0;
  }
  //5.查看队列中元素的个数
  myPriorityQueue.prototype.size = function () {
    return this.items.length;
  }
  //6.toString
  myPriorityQueue.prototype.toString = function () {
    var result = '';
    for (var i = 0; i < this.items.length; i++) {
      result += this.items[i].element + '---' + this.items[i].priority + ' ';
    }
    return result;
  }
}